package sort;

import comment.Comment;

/**
 *create by tbj
 *	
 *	1.利用随机的v，随机种子来比较，解决了 近乎排好序的数组。
 *	2.三路解决含有大量重复元素的情况，相等时，不用管。
 */
public class QuickSort_Three {
	private static void _sort(int[] a,int l,int r){
		if(l >= r ){
			return;
		}
		Comment.swapIntArr(a, l, (int)Math.random()*(r-l+1)+l);//优化语句,见one
		int v=a[l];
		int lt=l,gt=r+1,i=l+1;
		while(i < gt){
			if(a[i]<v){
				Comment.swapIntArr(a, i, lt+1);
				i++;
				lt++;
			}else if(a[i]>v){
				Comment.swapIntArr(a, i, gt-1);
				gt--;
			}else{
				i++;
			}
		}
		Comment.swapIntArr(a, l, lt);
		_sort(a, l, lt-1);//上面交换了下，lt变成是等于v的元素位置
		_sort(a, gt, r);
	}
	public static void sort(int[] a){
		int n=a.length;
		_sort(a,0,n-1);
	}
	public static void main(String[] args) {
		int[] a=Comment.getSortIntArr();
		QuickSort_Three.sort(a);
		for (int i : a) {
			System.out.print(i+" ");
		}
	}
}
